/*
 * @lc app=leetcode.cn id=691 lang=c
 *
 * [691] 贴纸拼词
 */

// @lc code=start
#define MIN(a, b) ((a) < (b) ? (a) : (b))

static int helper(int mask, int *dp, char **stickers, int stickersSize, char *target)
{
    int m = strlen(target);
    if (dp[mask] != -1)
    {
        return dp[mask];
    }
    dp[mask] = m + 1;
    // 遍历获取单词 stickers[j] ，通过cnt字符串表记录此单词包含的字母
    // mask数字的二进制第i位如果为1表示缺少字母 target[i]
    for (int j = 0; j < stickersSize; j++)
    {
        int left = mask;
        int cnt[26]; // 记录当前单词 stickers[j] 包含所有的字母
        int len = strlen(stickers[j]);
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < len; i++)
        {
            cnt[stickers[j][i] - 'a']++;
        }
        // 遍历target[i]，如果单词 stickers[j] 包含字母 target[i]，则记录到 mask 的二进制第i位值为0
        for (int i = 0; i < m; i++)
        {
            if ((mask >> i & 1) && cnt[target[i] - 'a'] > 0)
            {                           // mask的二进制第i位如果为1，且单词 stickers[j] 包含字母 target[i]
                cnt[target[i] - 'a']--; // 扣除使用的字母
                left ^= 1 << i;         // left的第 i+1 位(及最高位)从1变为0，因为初始mask为m个1的二进制数字
            }
        }
        if (left < mask)
        {
            dp[mask] = MIN(dp[mask], helper(left, dp, stickers, stickersSize, target) + 1);
        }
    }
    return dp[mask];
};

int minStickers(char **stickers, int stickersSize, char *target)
{
    int m = strlen(target);
    int *dp = (int *)malloc(sizeof(int) * (1 << m));
    memset(dp, -1, sizeof(int) * (1 << m));
    dp[0] = 0;
    int res = helper((1 << m) - 1, dp, stickers, stickersSize, target); // 初始mask为m个1的二进制数字
    free(dp);
    return res > m ? -1 : res;
}

// 定义函数 dp(mask)来求解不同状态的最小贴纸数，输入是某个子序列 mask，输出是拼出该子序列的最小贴纸数。

// 计算拼出 mask 所需的最小贴纸数时，需要选取最优的 sticker 让其贡献部分字符，未被 sticker 覆盖的其他字符 left 需要用动态规划继续计算。

// @lc code=end
